public class RepeatedSubstring {
    /*
    * 重复的子字符串
    * 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
    *
    * 1 <= s.length <= 10(4)
    * s 由小写英文字母组成
    * */
    public static void main(String[] args){

    }

    // KMP: 利用next数组的特性
    public boolean solution1(String s){
        if(s.length() == 1)
            return false;
        int[] next = new int[s.length()];
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(j) != s.charAt(i))
                j = next[j-1];
            if(s.charAt(j) == s.charAt(i))
                j++;
            next[i] = j;
        }
        return next[s.length()-1] > 0 && s.length() % (s.length() - next[s.length()-1]) == 0;
    }
}
